package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-10 16:00
 * @description: Functions of this class is
 * 最好的方法：拼接法 空间复杂度O（1） 题解：
 * class Solution {
 *     public Node copyRandomList(Node head) {
 *         if(head!=null){
 *             //空间复杂度为O（1）
 *             Node cur=head;
 *             //先进行链表的拼接
 *             //1-2-3-4-5  变成：1-1-2-2-3-3-4-4-5-5
 *             //先进行next指针的复制
 *             while(cur!=null){
 *                 Node p=new Node(cur.val);
 *                 p.next=cur.next;
 *                 cur.next=p;
 *                 cur=p.next;//向后走两个，跳过新建立的节点
 *             }
 *             cur=head;
 *             //然后进行random指针的复制
 *             while(cur!=null){
 *                 if(cur.random!=null){
 *                     //如果原链表中存在random结点
 *                     cur.next.random=cur.random.next;//就将新节点（当前节点下一个）指向当前节点random指向元素的复制新节点
 *                 }
 *                 cur=cur.next.next;//然后跳转到下一个原链表指针中！！！！！！！这里千万不能忘记了是走两步！！！！！！！！是遍历原数组！！！！！！！
 *             }
 *             //然后进行两个链表的拆分
 *             cur=head.next;//！！！！！！！！！从复制链表头节点开始遍历！！！！！！！！！
 *             //分开成两条链
 *             Node ans=head.next;//复制链表头节点
 *             Node pre=head;//原链表头节点
 *             while(cur.next!=null){
 *                 //！！！！！！！！！！！！！！！！这里要注意就是要先走pre指针，因为pre在前，如果cur指针先走的话就会导致覆盖了前面的pre指针
 *                 pre.next=pre.next.next;
 *                 cur.next=cur.next.next;
 *                 pre=pre.next;
 *                 cur=cur.next;
 *             }
 *             pre.next=null;//要单独处理一下原链表最后一个节点next指针，因为在循环中没有处理还是连着新链表的最后一个节点
 *             return ans;
 *         }
 *         return head;
 *     }
 * }
 *
 **/
public class NoNo复杂链表的复制 {
    //两种方法时间复杂度都是ok的，就是空间复杂度有不同
    public static void main(String[] args) {

    }
    /**
     * 哈希表法空间复杂度O（n）不太好，但是比较好理解：
     * class Solution {
     *     if(head!=null){
     *             //哈希表法，不太好，先试试
     *             HashMap<Node,Node>map=new HashMap<Node,Node>();
     *             Node cur=head;
     *             while(cur!=null){
     *                 //先遍历一遍，进行复杂链表值的复制
     *                 map.put(cur,new Node(cur.val));
     *                 cur=cur.next;
     *             }
     *             cur=head;
     *             while(cur!=null){
     *                 //然后再遍历一遍进行next和random指针的复制
     *                 map.get(cur).next=map.get(cur.next);
     *                 map.get(cur).random=map.get(cur.random);//直接用hashMap找到当前节点的下一个随即指针
     *                 cur=cur.next;
     *             }
     *             return map.get(head);
     *         }
     *         return head;
     * }

     */
}